package com.wpp.algorithm.lagou.sort;

/**
 * @description: 快速排序
 *  时间复杂度 ：O(nlogn)
 * @author: WangPengPeng
 * @create: 2021-11-11 21:30
 **/
public class QuickSort implements SortInterface{


    /**
     * 分治
     * @param arr
     */
    @Override
    public void sort(int[] arr) {
        quickSort(arr,0,arr.length - 1);
    }

    private void quickSort(int[] arr,int leftIndex,int rightIndex) {
        if (leftIndex >= rightIndex) {
            return;
        }
        int pivotIndex = partition(arr,leftIndex,rightIndex);
       // int pivotIndex = partition(arr,leftIndex,rightIndex);
        quickSort(arr,leftIndex,pivotIndex - 1);
        quickSort(arr,pivotIndex + 1,rightIndex);

    }

    /**
     * 分治（双边循环法）
     * @param arr
     * @param beginIndex
     * @param endIndex
     * @return
     */
    private int getPivot(int[] arr,int beginIndex,int endIndex) {
        int pivot = arr[beginIndex];
        int leftChild = beginIndex;
        int rightChild = endIndex;

        while (leftChild != rightChild) {
            if (leftChild < rightChild && arr[rightChild] > pivot) {
                rightChild--;
            }
            if (leftChild < rightChild && arr[leftChild] <= pivot) {
                leftChild++;
            }
            if (leftChild < rightChild) {
                int temp = arr[leftChild];
                arr[leftChild] = arr[rightChild];
                arr[rightChild] = temp;
            }
        }
        arr[beginIndex] = arr[leftChild];
        arr[leftChild] = pivot;

        return leftChild;
    }


    /**
     * 单边循环
     * @param arr
     * @param startIndex
     * @param endIndex
     * @return
     */
    private static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第1个位置（也可以选择随机位置）的元素作为基准元素
        int pivot = arr[startIndex];
        int mark = startIndex;
        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arr[i] < pivot) {
                mark++;
                int p = arr[mark];
                arr[mark] = arr[i];
                arr[i] = p;
            }
        }
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
     }
}
